package org.usmile.algorithms.learn.graph.weighted;

import java.util.*;

public class Dijkstra {

    public int distance(WeightedAdjSet graph, int source, int target) {
        int[] distance = new int[graph.getV()];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[source] = 0;
        boolean[] visited = new boolean[graph.getV()];

        while (true) {
            int currDistance = Integer.MAX_VALUE;
            int curr = -1;
            // 找到当前没有访问的最短路径节点
            for (int v = 0; v < graph.getV(); v++) {
                if (!visited[v] && distance[v] < currDistance) {
                    currDistance = distance[v];
                    curr = v;
                }
            }
            if (curr == -1) {
                break;
            }
            // 确认这个节点的最短路径就是当前大小
            visited[curr] = true;
            // 根据这个节点的最短路径大小，更新其他节点的路径大小
            for (int w : graph.adj(curr)) {
                if (!visited[w]) {
                    if (distance[curr] + graph.getWeight(curr, w) < distance[w]) {
                        distance[w] = distance[curr] + graph.getWeight(curr, w);
                    }
                }
            }
        }

        return distance[target];
    }

    public int distance1(WeightedAdjSet graph, int source, int target) {
        int[] distance = new int[graph.getV()];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[source] = 0;
        boolean[] visited = new boolean[graph.getV()];
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        priorityQueue.add(new int[]{source, 0});
        while (!priorityQueue.isEmpty()) {
            // 找到当前没有访问的最短路径节点
            int curr = priorityQueue.poll()[0];
            if (visited[curr]) {
                continue;
            }
            // 确认这个节点的最短路径就是当前大小
            visited[curr] = true;
            // 根据这个节点的最短路径大小，更新其他节点的路径大小
            for (int w : graph.adj(curr)) {
                if (!visited[w]) {
                    if (distance[curr] + graph.getWeight(curr, w) < distance[w]) {
                        distance[w] = distance[curr] + graph.getWeight(curr, w);
                        priorityQueue.add(new int[]{w, distance[w]});
                    }
                }
            }
        }

        return distance[target];
    }

    public List<Integer> distance2(WeightedAdjSet graph, int source, int target) {
        int[] distance = new int[graph.getV()];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[source] = 0;
        int[] prevs = new int[graph.getV()];
        Arrays.fill(prevs, -1);
        boolean[] visited = new boolean[graph.getV()];
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        priorityQueue.add(new int[]{source, 0});
        while (!priorityQueue.isEmpty()) {
            // 找到当前没有访问的最短路径节点
            int curr = priorityQueue.poll()[0];
            if (visited[curr]) {
                continue;
            }
            // 确认这个节点的最短路径就是当前大小
            visited[curr] = true;
            // 根据这个节点的最短路径大小，更新其他节点的路径大小
            for (int w : graph.adj(curr)) {
                if (!visited[w]) {
                    if (distance[curr] + graph.getWeight(curr, w) < distance[w]) {
                        distance[w] = distance[curr] + graph.getWeight(curr, w);
                        priorityQueue.add(new int[]{w, distance[w]});
                        prevs[w] = curr;
                    }
                }
            }
        }

        if (prevs[target] == -1) {
            return new ArrayList<>();
        }

        LinkedList<Integer> result = new LinkedList<>();
        while (target != source) {
            result.addFirst(target);
            target = prevs[target];
        }
        result.addFirst(source);

        return result;
    }

    public static void main(String[] args) {
        WeightedAdjSet graph = new WeightedAdjSet(4);
        graph.addEdge(0, 1, 1);
        graph.addEdge(0, 3, 9);
        graph.addEdge(1, 2, 2);
        graph.addEdge(1, 3, 4);
        graph.addEdge(2, 3, 3);

        System.out.println(new Dijkstra().distance2(graph, 0, 3));
    }
}
